// bfs 解决 FloodFill 算法
// 类似于二叉树的层序遍历，借助队列存放坐标
// 出队时上下左右四个方向扫描，将具有相同性质的坐标加入队列，循环直至队列为空即完成了 FloodFill 算法
// 经典题目 - 找连通块的数量，通过遍历的方式每找到一个符合要求的坐标，就使用 bfs 搜索全部的连同区域，并且标记

// 例题 2：
// 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
// 岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
//
//        此外，你可以假设该网格的四条边均被水包围。
//
//        示例 1：
//
//        输入：grid = [
//        ["1","1","1","1","0"],
//        ["1","1","0","1","0"],
//        ["1","1","0","0","0"],
//        ["0","0","0","0","0"]
//        ]
//        输出：1
//        示例 2：
//
//        输入：grid = [
//        ["1","1","0","0","0"],
//        ["1","1","0","0","0"],
//        ["0","0","1","0","0"],
//        ["0","0","0","1","1"]
//        ]
//        输出：3
//
//
//        提示：
//
//        m == grid.length
//        n == grid[i].length
//        1 <= m, n <= 300
//        grid[i][j] 的值为 '0' 或 '1'

// 解题思路：
// 遍历数组，每找到一块陆地，就用 bfs 方式搜索并标记

import java.util.LinkedList;
import java.util.Queue;

public class NumIslands {
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    boolean[][] check;
    int m = 0;
    int n = 0;
    public int numIslands(char[][] grid) {
        m = grid.length;
        n = grid[0].length;
        check = new boolean[m][n];
        Queue<int[]> queue = new LinkedList<>();
        int ret = 0;
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(grid[i][j] == '1' && check[i][j] == false){
                    ret++;
                    bfs(grid, i, j);
                }
            }
        }
        return ret;
    }
    public void bfs(char[][] grid, int i, int j){
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[] {i, j});
        check[i][j] = true;
        while(!queue.isEmpty()){
            int[] point = queue.poll();
            int a = point[0];
            int b = point[1];
            for(int k = 0; k < 4; k++){
                int x = a + dx[k];
                int y = b + dy[k];
                if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1' && check[x][y] == false){
                    queue.offer(new int[] {x, y});
                    check[x][y] = true;
                }
            }
        }
    }
}
